{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Similar RGB Color"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: similarRGB"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #相似 RGB 颜色"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>RGB 颜色 <code>\"#AABBCC\"</code>&nbsp;可以简写成&nbsp;<code>\"#ABC\"</code> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"#15c\"</code>&nbsp;其实是&nbsp;<code>\"#1155cc\"</code> 的简写。</li>\n",
    "</ul>\n",
    "\n",
    "<p>现在，假如我们分别定义两个颜色 <code>\"#ABCDEF\"</code>&nbsp;和&nbsp;<code>\"#UVWXYZ\"</code>，则他们的相似度可以通过这个表达式&nbsp;<code>-(AB - UV)^2 -&nbsp;(CD - WX)^2 -&nbsp;(EF - YZ)^2</code>&nbsp;来计算。</p>\n",
    "\n",
    "<p>那么给你一个按 <code>\"#ABCDEF\"</code> 形式定义的字符串 <code>color</code> 表示 RGB 颜色，请你以字符串形式，返回一个与它相似度最大且可以简写的颜色。（比如，可以表示成类似 <code>\"#XYZ\"</code> 的形式）</p>\n",
    "\n",
    "<p><strong>任何</strong> 具有相同的（最大）相似度的答案都会被视为正确答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>color = \"#09f166\"\n",
    "<strong>输出：</strong>\"#11ee66\"\n",
    "<strong>解释：</strong> \n",
    "因为相似度计算得出 -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73\n",
    "这已经是所有可以简写的颜色中最相似的了\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>color = \"#4e3fe1\"\n",
    "<strong>输出：</strong>\"#5544dd\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>color.length == 7</code></li>\n",
    "\t<li><code>color[0] == '#'</code></li>\n",
    "\t<li>对于任何 <code>i &gt; 0</code>，<code>color[i]</code> 都是一个在范围 <code>['0', 'f']</code> 内的 16 进制数</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [similar-rgb-color](https://leetcode.cn/problems/similar-rgb-color/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [similar-rgb-color](https://leetcode.cn/problems/similar-rgb-color/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"#09f166\"', '\"#4e3fe1\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        res = \"#\"\n",
    "        for i in range(1, 7, 2):\n",
    "            cur = int(color[i: i+2], 16)\n",
    "            ####### 最后的结果都是 00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff。在10进制中，都是17的倍数\n",
    "            a = cur // 17\n",
    "            b = cur % 17\n",
    "            if b > 8:       #如果超过了一半\n",
    "                a += 1\n",
    "            \n",
    "            num = a *17     #结果，10进制是多大\n",
    "            #####10进制转换成16进制\n",
    "            res += hex(num)[2:] if num != 0 else \"00\" \n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        def check(c):\n",
    "            num = int('0x' + c,16)\n",
    "            ans = '00'\n",
    "            dis = inf\n",
    "            for w in \"0123456789abcdef\":\n",
    "                cur = abs(int('0x' + w*2,16) - num)\n",
    "                if cur < dis:\n",
    "                    dis = cur\n",
    "                    ans = w*2\n",
    "            return ans\n",
    "        return f\"#{check(color[1:3])}{check(color[3:5])}{check(color[5:7])}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        ans = '#'\n",
    "        #\n",
    "        for i in range(1, 7, 2):\n",
    "            num = int(color[i:i+2], 16)\n",
    "            zps = color[i]\n",
    "            tmp = int(zps + zps, 16)\n",
    "            dst = (num - tmp)**2\n",
    "            #小+大\n",
    "            if tmp > 16 and tmp > num:\n",
    "                #tmp -= 17\n",
    "                if (num - tmp + 17)**2 < dst:\n",
    "                    dst = (num - tmp)**2\n",
    "                    zps = hex(tmp-17)[2]\n",
    "            if tmp < 238 and tmp < num:\n",
    "                #tmp += 17\n",
    "                if (num - tmp - 17)**2 < dst:\n",
    "                    #dst = (num - tmp)**2\n",
    "                    zps = hex(tmp+17)[2]\n",
    "            ans += zps + zps\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        def similarity(hex1, hex2):\n",
    "            r1, g1, b1 = hex1 >> 16, (hex1 >> 8) % 256, hex1 % 256\n",
    "            r2, g2, b2 = hex2 >> 16, (hex2 >> 8) % 256, hex2 % 256\n",
    "            return -(r1 - r2)**2 - (g1 - g2)**2 - (b1 - b2)**2\n",
    "\n",
    "        hex1 = int(color[1:], 16)\n",
    "        ans = 0\n",
    "        for r in range(16):\n",
    "            for g in range(16):\n",
    "                for b in range(16):\n",
    "                    hex2 = 17 * r * (1 << 16) + 17 * g * (1 << 8) + 17 * b\n",
    "                    if similarity(hex1, hex2) > similarity(hex1, ans):\n",
    "                        ans = hex2\n",
    "\n",
    "        return '#{:06x}'.format(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        ans = ''\n",
    "        a, b, c = int(color[1:3], 16), int(color[3:5], 16), int(color[5:], 16)\n",
    "        dic = '0123456789abcdef'\n",
    "        tmp = inf\n",
    "        for i in range(16):\n",
    "            for j in range(16):\n",
    "                for k in range(16):\n",
    "                    d = pow(17 * i - a, 2) + pow(17 * j - b, 2) + pow(17 * k - c, 2)\n",
    "                    if d < tmp:\n",
    "                        tmp = d\n",
    "                        x, y, z = dic[i], dic[j], dic[k]\n",
    "                        ans = f'#{x}{x}{y}{y}{z}{z}'\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        _res = '#'\n",
    "        for i in range(1, len(color), 2):\n",
    "            temp = int(color[i:i + 2], 16)\n",
    "            a = temp // 17\n",
    "            b = temp % 17\n",
    "            if b > 8:\n",
    "                a += 1\n",
    "            num = a * 17\n",
    "            if num != 0:\n",
    "                _res += hex(num)[2:]\n",
    "            else:\n",
    "                _res += '00'\n",
    "        return _res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        ans = '#'\n",
    "        #\n",
    "        for i in range(1, 7, 2):\n",
    "            num = int(color[i:i+2], 16)\n",
    "            zps = color[i] + color[i]\n",
    "            tmp = int(zps, 16)\n",
    "            dst = (num - tmp)**2\n",
    "            #小+大\n",
    "            if tmp > 16:\n",
    "                #tmp -= 17\n",
    "                if (num - tmp + 17)**2 < dst:\n",
    "                    dst = (num - tmp)^2\n",
    "                    zps = hex(tmp-17)[2:]\n",
    "            if tmp < 255:\n",
    "                #tmp += 17\n",
    "                if (num - tmp - 17)**2 < dst:\n",
    "                    dst = (num - tmp)**2\n",
    "                    zps = hex(tmp+17)[2:]\n",
    "            ans += zps\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        def calc_dist(segment, target):\n",
    "            return (int(segment, 16) - int(target, 16)) ** 2\n",
    "        \n",
    "        def closest_shorthand(segment):\n",
    "            min_dist = float('inf')\n",
    "            best = ''\n",
    "            for i in range(16):\n",
    "                shorthand = \"{:x}\".format(i) * 2\n",
    "                dist = calc_dist(segment, shorthand)\n",
    "                if dist < min_dist:\n",
    "                    min_dist = dist\n",
    "                    best = shorthand\n",
    "            return best\n",
    "        \n",
    "        r = closest_shorthand(color[1:3])\n",
    "        g = closest_shorthand(color[3:5])\n",
    "        b = closest_shorthand(color[5:7])\n",
    "\n",
    "        return '#' + r + g + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        def convert(comp):\n",
    "            q,r=divmod(int(comp,16),17)\n",
    "            if r>8:q+=1\n",
    "            return '{:02x}'.format(17*q)\n",
    "        \n",
    "        return \"#\"+convert(color[1:3])+convert(color[3:5])+convert(color[5:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "      def f(comp):\n",
    "        q, r = divmod(int(comp, 16), 17)\n",
    "        if r > 8: q += 1\n",
    "        return '{:02x}'.format(17 * q)\n",
    "\n",
    "      return '#' + f(color[1:3]) + f(color[3:5]) + f(color[5:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        return '#' + ''.join(map(lambda x: hex((int(x, 16) + 8) // 17)[2:] * 2, (color[i: i + 2] for i in range(1, 7, 2))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        ans = '#'\n",
    "        #\n",
    "        for i in range(1, 7, 2):\n",
    "            num = int(color[i:i+2], 16)\n",
    "            zps = color[i]\n",
    "            tmp = int(zps + zps, 16)\n",
    "            dst = (num - tmp)**2\n",
    "            #小+大\n",
    "            if tmp > num:\n",
    "                #tmp -= 17\n",
    "                if tmp > 16 and (num - tmp + 17)**2 < dst:\n",
    "                    #dst = (num - tmp)**2\n",
    "                    zps = hex(tmp-17)[2]\n",
    "            else:\n",
    "                #tmp += 17\n",
    "                if tmp < 238 and (num - tmp - 17)**2 < dst:\n",
    "                    #dst = (num - tmp)**2\n",
    "                    zps = hex(tmp+17)[2]\n",
    "            ans += zps + zps\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        return '#'+''.join(map(lambda x:hex((int(x,16)+8)//17)[2:]*2,(color[i:i+2] for i in range(1,7,2))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        def f(comp):\n",
    "            q, r = divmod(int(comp, 16), 17)\n",
    "            if r > 8: q += 1\n",
    "            return '{:02x}'.format(17 * q)\n",
    "\n",
    "        return '#' + f(color[1:3]) + f(color[3:5]) + f(color[5:])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "\n",
    "        def getClosest(s: str) -> str:\n",
    "            hexdigits = \"0123456789abcdef\"\n",
    "            q, r = divmod(int(s, 16), 17)\n",
    "            if r > 8: q += 1\n",
    "            return hexdigits[q]\n",
    "\n",
    "        return \"#\" + getClosest(color[1:3]) + getClosest(color[3:5]) + getClosest(color[5:7])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        def f(comp):\n",
    "            q, r = divmod(int(comp, 16), 17)\n",
    "            if r > 8: q += 1\n",
    "            return '{:02x}'.format(17 * q)\n",
    "\n",
    "        return '#' + f(color[1:3]) + f(color[3:5]) + f(color[5:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def similarRGB(self, color):\n",
    "        def similarity(hex1, hex2):\n",
    "            r1, g1, b1 = hex1 >> 16, (hex1 >> 8) % 256, hex1 % 256\n",
    "            r2, g2, b2 = hex2 >> 16, (hex2 >> 8) % 256, hex2 % 256\n",
    "            return -(r1 - r2)**2 - (g1 - g2)**2 - (b1 - b2)**2\n",
    "\n",
    "        hex1 = int(color[1:], 16)\n",
    "        ans = 0\n",
    "        for r in range(16):\n",
    "            for g in range(16):\n",
    "                for b in range(16):\n",
    "                    hex2 = 17 * r * (1 << 16) + 17 * g * (1 << 8) + 17 * b\n",
    "                    if similarity(hex1, hex2) > similarity(hex1, ans):\n",
    "                        ans = hex2\n",
    "\n",
    "        return '#{:06x}'.format(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "k=['00','11','22','33','44','55','66','77','88','99','aa','bb','cc','dd','ee','ff']\n",
    "ks=[0,17,34,51,68,85,102,119,136,153,170,187,204,221,238,256]\n",
    "class Solution:\n",
    "    def similarRGB(self, color: str) -> str:\n",
    "        def getNum(t):\n",
    "            if t.isdigit():return int(t)\n",
    "            return 10+ord(t)-ord('a')\n",
    "        def getRgb(t):\n",
    "            print(t)\n",
    "            p=bisect.bisect_right(ks,t)\n",
    "            if p==16:return 15\n",
    "            if ks[p]-t<=t-ks[p-1]:return p\n",
    "            return p-1\n",
    "        res='#'\n",
    "        res+=k[getRgb(getNum(color[1])*16+getNum(color[2]))]\n",
    "        res+=k[getRgb(getNum(color[3])*16+getNum(color[4]))]\n",
    "        res+=k[getRgb(getNum(color[5])*16+getNum(color[6]))]\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 枚举\n",
    "    def similarRGB1(self, color):\n",
    "        def similarity(hex1, hex2):\n",
    "            r1, g1, b1 = hex1 >> 16, (hex1 >> 8) % 256, hex1 % 256\n",
    "            r2, g2, b2 = hex2 >> 16, (hex2 >> 8) % 256, hex2 % 256\n",
    "            return -(r1 - r2)**2 - (g1 - g2)**2 - (b1 - b2)**2\n",
    "\n",
    "        hex1 = int(color[1:], 16)\n",
    "        ans = 0\n",
    "        for r in range(16):\n",
    "            for g in range(16):\n",
    "                for b in range(16):\n",
    "                    hex2 = 17 * r * (1 << 16) + 17 * g * (1 << 8) + 17 * b\n",
    "                    if similarity(hex1, hex2) > similarity(hex1, ans):\n",
    "                        ans = hex2\n",
    "\n",
    "        return '#{:06x}'.format(ans)\n",
    "        \n",
    "    # 独立性 + 枚举\n",
    "    def similarRGB(self, color):\n",
    "        def f(comp):\n",
    "            q, r = divmod(int(comp, 16), 17)\n",
    "            if r > 8: q += 1\n",
    "            return '{:02x}'.format(17 * q)\n",
    "\n",
    "        return '#' + f(color[1:3]) + f(color[3:5]) + f(color[5:])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
